package syf.rank;

import java.net.Socket;
import java.util.Arrays;

public class Review {
    public static void main(String[] args) {
        int max=8;
        int[]arr=new int[max];
        for (int i=0;i<max;i++){
            arr[i]= (int) (Math.random()*100);
        }
//        System.out.println(Arrays.toString(arr));
//        int[] arr={-9,78,0,80,-567,70};
        long start=System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
//        Bubble(arr);
//        choose(arr);
//        insert(arr);
//        shell1(arr);
//        shell2(arr);
//        quick(arr,0,arr.length-1);
        int[]tmp=new int[arr.length];
        merge_1(arr,0,arr.length-1,tmp);
        System.out.println(Arrays.toString(arr));
        long end=System.currentTimeMillis();
        System.out.println(end-start);
    }
    public static void Bubble(int[]arr){
        int tmp;
        boolean flag;
        int index;
        for (int i=0;i< arr.length;i++){
            index=0;
            flag=true;
            for (int j=1;j<arr.length-i;j++){
               if (arr[index]>arr[j]){
                   tmp=arr[index];
                   arr[index]=arr[j];
                   arr[j]=tmp;
                   flag=false;
               }
               index++;
            }
            if (flag)
                break;
        }
//        System.out.println(Arrays.toString(arr));
    }
    public static void choose(int[]arr){
        int tmp;
        int index;
        for (int i=0;i< arr.length-1;i++){
            tmp=arr[i];
            index=i;
            for (int j=i+1;j<arr.length;j++){
                if (tmp>arr[j]){
                    tmp=arr[j];
                    index=j;
                }
            }
            arr[index]=arr[i];
            arr[i]=tmp;
        }
//        System.out.println(Arrays.toString(arr));
    }
    public static void insert(int[]arr){
//        System.out.println(Arrays.toString(arr));
        int insertVal;
        int insertIndex;
        for (int i=0;i<arr.length-1;i++){
            insertIndex=i;
            insertVal=arr[i+1];
            while (insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1]=insertVal;
        }
//        System.out.println(Arrays.toString(arr));
    }
    public static void shell1(int[]arr){
        int tmp;
//        System.out.println(Arrays.toString(arr));
        for (int gap=arr.length/2;gap>0;gap/=2){
            for (int i=gap;i<arr.length;i++){
                for (int j=i-gap;j>=0;j-=gap){
                    if (arr[j+gap]<arr[j]){
                        tmp=arr[j+gap];
                        arr[j+gap]=arr[j];
                        arr[j]=tmp;
                    }
                }
            }
        }
//        System.out.println(Arrays.toString(arr));
    }
    public static void shell2(int[]arr){
        int insertIndex;
        int insertVal;
        for (int gap=arr.length/2;gap>0;gap/=2){
            for (int i=gap;i<arr.length;i++){
                insertIndex=i;
                insertVal=arr[i];
                    while (insertIndex-gap>=0&&arr[insertIndex-gap]>arr[insertIndex]){
                        arr[insertIndex]=arr[insertIndex-gap];
                        insertIndex-=gap;
                    }
                arr[insertIndex]=insertVal;
            }
        }
    }
    public static int[] quick(int[] arr,int left,int right){
        int mid =arr[(left+right)/2];
        int tmp;
        int l=left;
        int r=right;
        while (l<r){
            while (arr[l]<mid){
                l++;
            }
            while (arr[r]>mid){
                r--;
            }
            if (l>=r)
                break;
            tmp=arr[l];
            arr[l]=arr[r];
            arr[r]=tmp;
            if (arr[l]==mid){
                r--;
            }
            if (arr[r]==mid){
                l++;
            }
        }
        if (l==r){
            l++;
            r--;
        }
        if (r>left){
            quick(arr,left,r);
        }
        if (l<right)
            quick(arr,l,right);
        return arr;
    }
    public static void merge_1(int[]arr,int left,int right,int[]tmp){
        int mid=(left+right)/2;
        if (left<right){
            merge_1(arr,left,mid,tmp);
            merge_1(arr,mid+1,right,tmp);
            merge_2(arr,left,mid,right,tmp);
        }
    }
    public static void merge_2(int[]arr,int left,int mid,int right,int[] tmp){
        int l=left;
        int r=mid+1;
        int t=0;
        while (l<=mid&&r<=right){
            if (arr[l]<=arr[r]){
                tmp[t++]=arr[l++];
            }else {
                tmp[t++]=arr[r++];
            }
        }
        while (l<=mid){
            tmp[t++]=arr[l++];
        }
        while (r<=right){
            tmp[t++]=arr[r++];
        }
        t=0;
        int index=left;
        while (index<=right){
            arr[index++]=tmp[t++];
        }
    }

}
